最接近的三数之和

[编程题]最接近的三数之和

热度指数：1486 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个数组 nums 和一个目标值 target ，请问从 nums 中选出三个数，使其之和尽量接近目标数，即三数之和与目标数只差绝对值尽可能小。

返回满足题面要求的三数之和。

数据范围：数组长度满足 $3 \le n \le 300 \$ ，数组中的值满足 $|nums[i]| \le 1000 \$ ，目标值满足 $|target| \le 10^4 \$ ，可以保证只有一个结果。

示例1

输入

[-1,2,1,-4],1

输出

说明

最接近 1 的三数之和是 -1+2+1 = 2

示例2

输入

[0,0,0],1

输出

说明

 只有一种选择 0+0+0

示例3

输入

[0,1,0,0],0

输出

算法知识视频讲解

Python 3

来牛客玩玩

class Solution:
    def ClosestSum(self , nums: List[int], target: int) -> int:
        # write code here
        nums.sort()
        res = nums[0]+nums[1]+nums[2]
        for i in range(len(nums)-2):
            start, end = i+1, len(nums)-1
            while start < end:
                tmp = nums[i]+nums[start]+nums[end]
                if abs(tmp-target) < abs(res-target):
                    res = tmp
                if tmp > target:
                    end -= 1
                elif tmp < target:
                    start += 1
                else:
                    return res
        return res

发表于 2022-07-24 17:14:00 回复(0)